Merge Sort
- Divide: Merge sort works by dividing the array into smaller subarrays.
- Conquer/Sort: It sorts the subarrays individually.
- Merge: Finally, merge the sorted subarrays to get the final sorted array.
Merge sort uses the concept of the divide and conquer method. In this approach, the problem is divided into a number of smaller modules, and the modules are solved individually. Then the results are combined to get the solution to the main problem.
There are three steps:
Video Lecture
Merge Sort Operation
The input array A[0 … n-1] contains n elements, and the indices range from 0 to n-1.
The array is divided into two parts: A[0 … (n/2) - 1] and A[n/2 … n-1]. The algorithm recursively divides the given array A until each sub-array contains a single element. After partitioning, the sub-arrays are sorted and merged recursively until a single sorted array is achieved.
The root node represents the main problem, while other nodes in the tree represent sub-problems. If n = 2k, where k = log n, the height of the tree is log n. Each level of the tree involves a maximum of n comparisons.
Algorithm
MergeSort(A[0]..A[n-1])
Input: Unsorted Array A containing n elements.
Output: Sorted Array A.
Step 1: Start.
Step 2: If the array has one or zero elements (n <= 1), it is already sorted. Return.
Step 3: Divide the array into two halves:
Left Half:A[0]..A[mid]Right Half:A[mid+1]..A[n-1]
Step 4: Recursively apply MergeSort to the left half.
Step 5: Recursively apply MergeSort to the right half.
Step 6: Merge the two sorted halves:
- Create two pointers, one for each half.
- Compare elements from both halves and copy the smaller element into a temporary array.
- Continue until all elements from both halves are merged into the temporary array.
Step 7: Copy the merged elements back into the original array.
Step 8: Output the sorted array.
Step 9: Stop.
Binary Search Code
#include <stdio.h>
/* Function to merge the subarrays of a[] */
void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;
int LeftArray[n1], RightArray[n2]; //temporary arrays
/* copy data to temp arrays */
for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];
i = 0; /* initial index of first sub-array */
j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */
while (i < n1 && j < n2)
{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}
while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}
void mergeSort(int a[], int beg, int end)
{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
/* Function to print the array */
void printArray(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
/* Function to get elements for the array */
void InputArray(int a[], int n)
{
int i;
printf("Enter the %d Elements\n",n);
for (i = 0; i < n; i++)
scanf("%d",&a[i]);
}
int main()
{
int a[100],n, key,i;
printf("Enter the size of the array \n");
scanf("%d",&n);
InputArray(a,n);
printf("Before sorting array elements are - \n");
printArray(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
printArray(a, n);
return 0;
}
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> L(n1);
std::vector<int> R(n2);
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.size() - 1);
for (int num : arr)
std::cout < num < " ";
std::cout < std::endl;
return 0;
}
public class MergeSort {
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
System.arraycopy(arr, left, L, 0, n1);
System.arraycopy(arr, mid + 1, R, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.length - 1);
for (int num : arr)
System.out.print(num + " ");
System.out.println();
}
}
def merge(arr, left, mid, right):
n1 = mid - left + 1
n2 = right - mid
L = arr[left:left + n1]
R = arr[mid + 1:mid + 1 + n2]
i = j = 0
k = left
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < n1:
arr[k] = L[i]
i += 1
k += 1
while j < n2:
arr[k] = R[j]
j += 1
k += 1
def merge_sort(arr, left, right):
if left < right:
mid = (left + right) // 2
merge_sort(arr, left, mid)
merge_sort(arr, mid + 1, right)
merge(arr, left, mid, right)
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr, 0, len(arr) - 1)
print(arr)
Analysis of Merge Sort
Time Complexity
In Merge Sort, the recursive process creates a tree of height log n, and there are log n + 1 levels in this tree. At each level, the algorithm performs a maximum of n comparisons. The total number of comparisons across all levels is the sum of comparisons at each level, resulting in a total of n.log n comparisons. Therefore, the time complexity is T(n) = n.log n = O(n.log n).
The basic operation of the Merge Sort algorithm is comparison. The time complexity is determined by how many times this comparison operation is performed. The running time T(n) for an input of size n is the sum of the time taken to divide the array into subarrays until we reach single elements and the time taken to sort and merge the sorted arrays.
Best Case: If the array is already sorted, the algorithm performs a minimum number of comparisons.
Worst Case: The worst-case scenario occurs during the sort and merge operations, particularly when elements are taken alternately from the two sorted input arrays. Merge Sort performs the maximum number of comparisons in this case.
Given that T(n) is the time taken to sort n elements using Merge Sort, the recurrence relation for Merge Sort is:
T(n) = T(n/2) + Tmerge(n)
Where Tmerge(n) is the time taken for the merge operation. In the worst case, the merge operation takes n-1 comparisons, so:
Tmerge(n) = n-1
Thus, the worst-case time complexity for Merge Sort is:
Tworst(n) = Tworst(n/2) + Tmerge(n)
Tworst(n) = Tworst(n/2) + (n-1)
According to the Master Theorem, Tworst(n/2) = n.log n, so:
Tworst(n) = n.log n + (n-1)
Tworst(n) = n.log n
Tworst(n) = O(n.log n)
Space Complexity
In the merge phase, elements from the two subarrays are copied into a newly created array. During the final merge step, the extra array size equals the input array size. Since the Merge Sort algorithm requires an additional array of size n for storing the n elements, the space complexity of Merge Sort is O(n).
